Skip to main content

300. 最长递增子序列

LeetCode 300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1： 输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2： 输入：nums = [0,1,0,3,2,3] 输出：4

示例 3： 输入：nums = [7,7,7,7,7,7,7] 输出：1

提示： 1 <= nums.length <= 2500 -104 <= nums[i] <= 104

进阶： 你可以设计时间复杂度为 O(n2) 的解决方案吗？ 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

思路（动态规划+二分查找）#

LIS：Longest Increasing Subset

  • 对于输入序列中的每个元素 X，分别找出找出以 X 结尾的 LIS，其中长度最长的，就是我们要找的最终 LIS
  • 为什么关注结尾？因为结尾决定了 LIS 所能有的最大值
  • 使其成为一个递增的数组，记录能形成 LIS 的所有元素
  • 一边遍历所有元素一边更新数组
    • 两种可能：
      1. nums[i] 比数组内所有元素都大 --> 它可以被放在 LIS 的末尾 --> append 一下，并且 LIS 的长度加 1
      2. 如果dp[i - 1] < nums[i] <= dp[i]，说明它需要替换大于等于 x 的dp[i]数字，以保证数组是一个递增的序列 --> 更新dp[i]
  • 我们可以通过二分查找，找到数组中需要被更新的那个数
public int lengthOfLIS(int[] nums) {
// 对于输入序列中的每个元素X，分别找出找出以X结尾的LIS，其中长度最长的，就是我们要找的最终LIS
int[] dp = new int[nums.length];
int size = 0;
// 新字符要么取代旧字符，要么加在dp末尾(i == size; size++;)
for (int i: nums){
int j = 0, k = size;
while (j != k){
int mid = j + (k - j)/2; // 找到被取代的字符的下标
if (dp[mid] < i){
j = mid + 1;
} else {
k = mid;
}
}
dp[j] = i;
if (j == size){
size++;
}
}
return size;
}

执行用时：4 ms, 在所有 Java 提交中击败了 84.11%的用户 内存消耗：37.8 MB, 在所有 Java 提交中击败了 91.22%的用户 心得：

  • 这道题是很经典的字符串类动态规划题目，顺便复习了一下动态规划代码模板；
  • 读题要仔细一点，把样例琢磨透了再开始写代码；
  • 勤能补拙。

Debug#

Binary search 时mid和dp[i]比较......不是和nums[i]！

代码优化#

class Solution {
public:
int lengthOfLIS(vector<int> nums) {
vector<int> d(nums.size(), INT_MAX);
for (auto num : nums) *lower_bound(d.begin(), d.end(), num) = num;
return lower_bound(d.begin(), d.end(), INT_MAX) - d.begin();
}
};

执行用时：8 ms, 在所有 C++ 提交中击败了 94.80%的用户 内存消耗：10.2 MB, 在所有 C++ 提交中击败了 62.42%的用户 心得：C++指针变量的妙用 hhhh 绝了绝了！不过空间复杂度还能再优化吗？好奇

扩展：树状数组解法#

阅读材料：树状数组简单易懂的详解FlushHip-CSDN 博客树状数组

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. Fenwick tree - Wikipedia

Create a binary indexed tree for the array [1, 2, 3, 4, 5] by inserting one by one: 440px-BITDemo.gif

Time complexity in big O notation#

Algorithm Average Worst case Space O(n) O(n) Search O(logn) O(logn) Insert O(logn) O(logn) Delete O(logn) O(logn)

Description#

Given an index in the array representing a vertex, the index of a vertex's parent or child is calculated through bitwise operations on the binary representation of its index. Each element of the array contains the pre-calculated sum of a range of values, and by combining that sum with additional ranges encountered during an upward traversal to the root, the prefix sum is calculated. When a table value is modified, all range sums which contain the modified value are in turn modified during a similar traversal of the tree. The range sums are defined in such a way that both queries and modifications to the table are executed in asymptotically equivalent time (${\displaystyle O(\log n)}$ in the worst case).

A Fenwick tree is most easily understood by considering a one-based array. Each element whose index is a power of 2 contains the sum of the first elements. Elements whose indices are the sum of two (distinct) powers of 2 contain the sum of the elements since the preceding power of 2. In general, each element contains the sum of the values since its parent in the tree, and that parent is found by clearing the least-significant bit in the index i i

To find the sum up to any given index, consider the binary expansion of the index, and add elements which correspond to each 1 bit in the binary form.

For example, say one wishes to find the sum of the first eleven values. Eleven is 10112 in binary. This contains three 1 bits, so three elements must be added: 10002, 10102, and 10112. These contain the sums of values 1–8, 9–10, and 11, respectively.

To modify the eleventh value, the elements which must be modified are 10112, 11002, 100002, and all higher powers of 2 up to the size of the array. These contain the sums of values 11, 9–12, and 1–16, respectively. The maximum number of elements which may need to be updated is limited by the number of bits in the size of the array.

......

Edit this page